package top.hkyzf.study.leetcode.array;

import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author 朱峰
 * @date 2022-1-19 9:22
 */
public class 存在重复元素II_219 {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if(nums.length < 2) {
            return false;
        }
        if(nums.length == 2) {
            return nums[0] == nums[1] && k >= 1;
        }
        for (int i = 0; i <= nums.length-2; i++) {
            for (int j = 1; j <= k; j++) {
                if(nums[i] == nums[i+j]) {
                    return true;
                }
                // 最后一位
                if(i+j == nums.length-1) {
                    break;
                }
            }
        }
        return false;
    }

    /**
     * 哈希表
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate1(int[] nums, int k) {
        Map<Integer, Integer> maps = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            if(maps.containsKey(val) && i - maps.get(val) <= k) {
                return true;
            }
            maps.put(val, i);
        }
        return false;
    }

    /**
     * 滑动窗口
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate2(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(i > k) {
                set.remove(nums[i - k - 1]);
            }
            if(!set.add(nums[i])) {
                return true;
            }
        }
        return false;
    }

    @Test
    public void testContainsNearbyDuplicate () {
        int [] nums = {1, 2, 3, 1, 2, 3};
        int k = 2;
        System.out.println(containsNearbyDuplicate2(nums, k));
    }
}
